package ds.linklist.firstlast;

/**双端链表最适合用来实现队列*/
public class LinkList {

	private Link first = null; // 这个null后来一直往后传啊传~~
	private Link last = null;
	// -----------------------------
	public boolean isEmpty(){
		return (first == null);
	}
	
	public void insertFirst(int value){
		Link newLink = new Link(value);
		if(isEmpty())
		{
			last = newLink;
		}
		newLink.next = first; // newLink -->(链接) old first
		first = newLink; // first ---> newLink
	}
	
	public void insertLast(int value){
		Link newLink = new Link(value);
		if(isEmpty())
		{
			first = last = newLink;
		}
		// newLink.next = null; 其实默认就是这个 0.0
		last.next = newLink;
		last = newLink;
	}
	
	public Link deleteFirst()
	{
		if(!isEmpty())
		{
			Link temp = first;
			first = first.next;
			return temp;
		}
		else
		{
			return null;
		}
	}
	
	public Link find(int key)
	{
		Link current = first;
		while(current!=null)
		{
			if(current.getData() == key)
				return current;
			else
				current=current.next;
		}
		return null;
	}
	
	public Link delete(int key)
	{		
		Link previous = null;
		Link current = first;
		
		while(current != null)
		{
			if(current.getData() == key)
			{
				Link temp = current;
				if(current == first)
					first = current.next;
				else
				{
					previous.next = current.next;
					current.next = null;
				}
				return temp;
			}
			else
			{
				previous = current;
				current = current.next;
			}
		}
		return null;
	}
	
	public Link getFirst()
	{
		return first;
	}
	
	public void displayList()
	{
		System.out.println("(first --> last):");
		Link current = first;
		while(current!=null)
		{
			current.displayLink();
			current = current.next;
		}
	}
}

class LinkListApp{
	public static void main(String[] args)
	{
		LinkList ll = new LinkList();
		ll.insertFirst(1);
		ll.insertFirst(2);
		ll.insertFirst(3);
		ll.insertLast(90);
		ll.insertLast(56);
		ll.insertLast(89);
		
		ll.displayList();
		
//		ll.find(6).displayLink();
//		ll.delete(7);
//		ll.delete(6);
//		ll.delete(4);
//		ll.displayList();
	}
}
